/**
 * Created With IntelliJ IDEA
 * Description:牛客网：CM11 链表分割
 * <a href="https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking">...</a>
 * User: DELL
 * Data: 2023-01-07
 * Time: 20:17
 */

//描述：现有一链表 ListNode pHead，给一定值x，编写一段代码将所有小于x的结点排在
//     其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
//思路：第一步先将原链表拆分为两个链表，第一个链表为小于x的所有结点，第二个链表为
//     大于等于x的所有结点，之后将两个链表拼接起来即可
import java.util.*;

class ListNode {
    public int val;
    public ListNode next;
    public ListNode (int val) {
        this.val = val;
    }
}
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        //判空处理
        if (pHead == null) {
            return null;
        }
        //小于x的新链表
        ListNode bHead = null;
        ListNode bLast = null;
        //大于等于x的新链表
        ListNode aHead = null;
        ListNode aLast = null;
        //对原链表进行分离
        ListNode cur = pHead;
        while (cur != null) {
            if (cur.val < x) {
                //链表为空时
                if (bHead == null) {
                    bHead = cur;
                    bLast = cur;
                } else { //不为空时
                    bLast.next = cur;
                    bLast = cur;
                }
            } else {
                //链表为空时
                if (aHead == null) {
                    aHead = cur;
                    aLast = cur;
                } else { //不为空时
                    aLast.next = cur;
                    aLast = cur;
                }
            }
            cur = cur.next;
        }
        //将两个新链表拼接为一个链表
        if (bHead == null) {
            return aHead;
        } else if (aHead == null) {
            return bHead;
        } else {
            bLast.next = aHead;
            //这一步很关键，否则可能会导致链表出现环
            aLast.next = null;
            return bHead;
        }
    }
}